#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        vector<bool> dp(n + 1);
        s = ' ' + s;
        dp[0] = true;
        unordered_map<string, int> hash;
        for (int i = 0; i < wordDict.size(); i++) hash[wordDict[i]]++;
        for (int right = 1; right <= n; right++)
        {
            for (int left = right; left >= 1; left--)
            {
                if (dp[left - 1] && hash.count(s.substr(left, right - left + 1)))
                {
                    dp[right] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};